package util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.TreeMap;

public class Huffman {

    private List alfabeto;
    private List nodosAlfabeto;
    private int numSimbolos;
    private FilaDePrioridade filaPrioridade;
    public static TreeMap codes;

    public Huffman(String frase) {
        alfabeto = new ArrayList();
        nodosAlfabeto = new ArrayList();
        this.filaPrioridade = new FilaDePrioridade(frase);
        this.numSimbolos = this.filaPrioridade.getSize();
        for (int i = 0; i < this.numSimbolos - 1; i++) {
            NodoHuffman x = this.filaPrioridade.extractMin();
            NodoHuffman y = this.filaPrioridade.extractMin();
            NodoHuffman nodo = new NodoHuffman("", x.frequencia + y.frequencia);
            nodo.setEsq(x);
            nodo.setDir(y);
            this.filaPrioridade.insert(nodo);
        }
    }

    private void geraCodeword(NodoHuffman nodo, String codeword) {
        if (nodo != null) {
            if (!nodo.valor.equals("")) {
                this.alfabeto.add(nodo.valor);
                this.nodosAlfabeto.add(nodo);
                nodo.codeword = codeword;
            }
            geraCodeword(nodo.getEsq(), codeword + "0");
            geraCodeword(nodo.getDir(), codeword + "1");
        }
    }

    private NodoHuffman procuraNodo(String simbolo) {
        NodoHuffman aux;
        for (int i = 0; i < this.numSimbolos; i++) {
            aux = (NodoHuffman) this.nodosAlfabeto.get(i);
            if (aux.valor.equals(simbolo)) {
                return aux;
            }
        }
        return null;
    }

    public List<Double> getComprimentos() {
        List comprimentos = new ArrayList();
        Collections.sort(this.alfabeto);
        NodoHuffman aux;
        for (int i = 0; i < this.numSimbolos; i++) {
            aux = procuraNodo((String) this.alfabeto.get(i));
            comprimentos.add(Double.valueOf("" + aux.codeword.length()));
        }
        return comprimentos;
    }

    public String toString() {
        geraCodeword(this.filaPrioridade.getMenor(), "");
        Collections.sort(this.alfabeto);
        String frase = "";
        NodoHuffman aux;
        codes = new TreeMap();
        for (int i = 0; i < this.numSimbolos; i++) {
            aux = procuraNodo((String) this.alfabeto.get(i));
            frase += aux.valor + " " + aux.codeword + "                   \t" + aux.codeword.length() + " \n";
            codes.put(aux.codeword, aux.valor);
        }
        return frase;
    }
}

class FilaDePrioridade {

    private int tamFila;
    private NodoHuffman menor;

    public FilaDePrioridade(String frase) {
        this.tamFila = 0;
        this.menor = null;
        char caractere;
        for (int i = 0; i < frase.length(); i++) {
            if (frase.charAt(i) != '*') {
                int freq = 1;
                caractere = frase.charAt(i);
                for (int j = frase.indexOf(caractere) + 1; j < frase.length(); j++) {
                    if (Character.toUpperCase(caractere) == Character.toUpperCase(frase.charAt(j))) {
                        freq++;
                    }
                }
                NodoHuffman nodo = new NodoHuffman(Character.toString(caractere).toLowerCase(), freq);
                insert(nodo);
                frase = frase.replace(caractere, '*');
                if (Character.isUpperCase(caractere)) {
                    frase = frase.replace(Character.toLowerCase(caractere), '*');
                } else {
                    frase = frase.replace(Character.toUpperCase(caractere), '*');
                }
            }
        }
    }

    public void insert(NodoHuffman nodo) {
        if (tamFila == 0) {
            this.menor = nodo;
            tamFila++;
        } else {
            NodoHuffman aux = this.menor;
            NodoHuffman aux2 = null;
            boolean adicionou = false;
            while (aux != null && adicionou == false) {
                aux2 = aux;
                if ((nodo.frequencia == aux.frequencia && !nodo.valor.equals("") && !aux.valor.equals("") && nodo.valor.compareTo(aux.valor) < 0) || nodo.frequencia < aux.frequencia) {
                    nodo.setProx(aux);
                    if (aux.getAnt() != null) {
                        aux.getAnt().setProx(nodo);
                        nodo.setAnt(aux.getAnt());
                    }
                    aux.setAnt(nodo);
                    adicionou = true;
                    if (aux == this.menor) {
                        this.menor = nodo;
                    }
                } else {
                    aux = aux.getProx();
                }

            }
            if (aux == null) {
                aux2.setProx(nodo);
                nodo.setAnt(aux2);
            }
            tamFila++;
        }
    }

    public NodoHuffman extractMin() {
        NodoHuffman prox = this.menor.getProx();
        NodoHuffman menor = this.menor;
        if (prox != null) {
            prox.setAnt(null);
            this.menor.setProx(null);
        }
        this.menor = prox;
        tamFila--;
        return menor;
    }

    public int getSize() {
        return tamFila;
    }

    public NodoHuffman getMenor() {
        return this.menor;
    }
}

class NodoHuffman {

    public String valor;
    public int frequencia;
    private NodoHuffman esq;
    private NodoHuffman dir;
    private NodoHuffman prox;
    private NodoHuffman ant;
    public String codeword;

    public NodoHuffman(String valor, int frequencia) {
        this.valor = valor;
        this.frequencia = frequencia;
        this.esq = null;
        this.dir = null;
        this.prox = null;
        this.ant = null;
        this.codeword = "";
    }

    public void setEsq(NodoHuffman nodo) {
        this.esq = nodo;
    }

    public void setDir(NodoHuffman nodo) {
        this.dir = nodo;
    }

    public void setProx(NodoHuffman nodo) {
        this.prox = nodo;
    }

    public void setAnt(NodoHuffman nodo) {
        this.ant = nodo;
    }

    public NodoHuffman getEsq() {
        return this.esq;
    }

    public NodoHuffman getDir() {
        return this.dir;
    }

    public NodoHuffman getProx() {
        return this.prox;
    }

    public NodoHuffman getAnt() {
        return this.ant;
    }
}
